import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}

class Solution {
    public int jump(int[] nums) {
        int target = nums.length - 1;
        int[] minCost = new int[nums.length];
        int maxIdx = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i + nums[i] > maxIdx) {
                for (int j = maxIdx + 1; j <= Math.min(i + nums[i], target); j++) {
                    minCost[j] = minCost[i] + 1;
                    if (j == target) {
                        return minCost[j];
                    }
                }
                maxIdx = i + nums[i];
            }
        }
        return 0;
    }
}

//解法优化（官方题解）
class Solution1 {
    public int jump(int[] nums) {
        int target = nums.length - 1;
        int steps = 0;
        int curMaxIdx = 0;
        int maxIdx = 0;
        for (int i = 0; i <= target; i++) {
            if (i > curMaxIdx) {
                curMaxIdx = maxIdx;
                steps++;
            }
            maxIdx = Math.max(maxIdx, i + nums[i]);
        }
        return steps;
    }
}